This invention relates to public key cryptosystems.
A popular type of cryptographic system is the public key cryptosystem. Such a system is characterized by a public key, and a private key which is determined by the public key but infeasible to compute. Such public key cryptosystems are used for public key messages such as secure key exchange, encryption, digital signatures, and authentications.
Examples of public key cryptosystems based on modular arithmetic are given in references 1, 2, and 3. Reference 1 is known in the art as RSA and has security based on the infeasibility of factoring large numbers. Reference 2 discloses a special case of the Elliptic Curve method, and is based on the difficulty of finding roots of points on an elliptic curve. Reference 3 is known as DSA, and is a variant of what is known in the art as ElGamal, and has security based on the infeasibility of the discrete logarithm problem.
The RSA, ElGamal, Elliptic Curve, and DSA methods all use a large integer modulus. With RSA, the modulus is a product of two primes which are secret and different for each user. The other methods are able to share one modulus among many users.
Public key cryptographic systems usually use intensive computation involving cryptovariables represented as large integers. These integers are typically hundreds of digits. The computations use modular arithmetic. A lot of computation time is usually spent doing modular reduction, that is, dividing. A small improvement in division can be valuable. Most of the cryptosystems are of modular exponential type, where the bulk of the computation involves raising an integer to some power with respect to some modulus. Methods for modular exponentials typically involve repeatedly multiplying two residues, and then doing a modular reduction on the product.
Crandall discloses a method for rapid modular reduction based on certain bits of the modulus being 1. Unfortunately, it is not known whether the discrete logarithm problem is secure for such a prime.
Some moduli are cryptographically weak. In the prior art, there are methods for producing weak moduli, but there is no simple test to determine the weakness of a given modulus. However, weak moduli are rare, and the National Institute of Standards and Technology (NIST) recommends a method for finding a prime modulus. It is regarded as a reliable way to obtain secure DSA parameters. It uses a sophisticated pseudorandom number generator, and the DSA modulus is determined by its length and the value of a 160-bit seed. The DSA uses a prime modulus of 512 bits or longer, and a generator of a multiplicative subgroup whose order is a 160-bit prime.
Prior art on large integer multipliers is disclosed in The Art of Computer Programing, Vol. 2, Seminumerical Algorithms, by Donald E. Knuth, Addison-Wesley, 1981. The classical algorithm requires execution time which is quadratic in the size of the input. Algorithms for subquadratic multipliers are also given.
Accordingly, there is a need for efficient modular reduction methods in cryptosystems. There is also a need for cryptographically strong moduli which allow particularly efficient modular reduction.